package GMDPRE

var Bn0 BN
var Bn1 = BN{1}

func DigAddDig(digA DigT, digB DigT) (DigT, DigT) {
	var tmp uint64
	var r DigT
	var c DigT

	tmp = uint64(digA) + uint64(digB)
	r = DigT(tmp & 0xffffffff)
	c = DigT(tmp >> 32)

	return c, r
}

func BnCmp(a *BN, b *BN, digs int) int {
	for i := digs - 1; i >= 0; i-- {
		if a[i] > b[i] {
			return 1
		} else if a[i] < b[i] {
			return -1
		}
	}
	return 0
}

func BnIsZero(a *BN, digs int) int {
	for i := 0; i < digs; i++ {
		if a[i] != 0 {
			return 0
		}
	}
	return 1
}

func BnGetBits(x *BN, digs int) int {
	for i := digs - 1; i >= 0; i-- {
		if x[i] > 0 {
			for j := 32; j > 0; j-- {
				if (x[i] >> (j - 1)) > 0 {
					return i*32 + j
				}
			}
		}
	}

	return 0
}

// BnAddBasic Add two big numbers of the same size.
// Compute c = a + b
func BnAddBasic(c *BN, a *BN, b *BN, digs int) DigT {
	var carry DigT = 0
	var ai DigT
	var bi DigT
	var tmp uint64

	for i := 0; i < digs; i++ {
		ai = a[i]
		bi = b[i]

		tmp = uint64(ai) + uint64(carry)
		c[i] = DigT(tmp & 0xffffffff)
		carry = DigT(tmp >> 32)

		tmp = uint64(c[i]) + uint64(bi)
		c[i] = DigT(tmp & 0xffffffff)
		carry += DigT(tmp >> 32)
	}

	return carry
}

// BnSubBasic Sub two big numbers of the same size.
// Compute c = a - b
func BnSubBasic(c *BN, a *BN, b *BN, digs int) DigT {
	var carry DigT = 0
	var ai DigT
	var bi DigT

	for i := 0; i < digs; i++ {
		ai = a[i]
		bi = b[i]

		c[i] = ai - bi - carry

		if carry == 1 {
			if bi < ai {
				carry = 0
			} else {
				carry = 1
			}
		} else {
			if bi <= ai {
				carry = 0
			} else {
				carry = 1
			}
		}
	}

	return carry
}

// Compute r = a * c + b
func bnMulDigAddBn(r *BN, a *BN, b *BN, c DigT, digs int) DigT {
	var carry DigT = 0
	var tmp uint64

	for i := 0; i < digs; i++ {
		tmp = uint64(a[i])*uint64(c) + uint64(b[i]) + uint64(carry)
		r[i] = DigT(tmp & 0xffffffff)
		carry = DigT(tmp >> 32)
	}

	return carry
}

func BnLshDig(c *BN, a *BN, d int, digs int) {
	if d <= 0 {
		*c = *a
		return
	}

	if d >= 8 {
		BnSetDig(c, 0, digs)
		return
	}

	i := digs - 1
	for ; i >= d; i-- {
		c[i] = a[i-d]
	}

	for ; i >= 0; i-- {
		c[i] = 0

	}
}

// BnLshBits computes c = a << b
func BnLshBits(c *BN, a *BN, b int, digs int) DigT {
	var carry DigT = 0
	var i int

	i = b / 32
	b = b % 32

	var tmp BN
	BnLshDig(&tmp, a, i, digs)

	if b == 0 {
		*c = tmp
		return 0
	}

	i = digs - 1
	carry = tmp[i] << b
	for i >= 1 {
		c[i] = (tmp[i] << b) | (tmp[i-1] >> (32 - b))
		i--
	}
	c[0] = tmp[0] << b

	return carry
}

// Compute bn = bn >> 32
func bnRsh32bit(bn *BN, digs int) {
	for i := 0; i < digs-1; i++ {
		bn[i] = bn[i+1]
	}
}

func BnSetDig(bn *BN, dig DigT, digs int) {
	bn[0] = dig
	for i := 1; i < digs; i++ {
		bn[i] = 0
	}
}

// BnMod computes r = a modulo m
func BnMod(r *BN, a *BN, m *BN, digs int) {
	var i int
	var tmp BN
	var n = BnGetBits(m, digs)

	*r = *a
	for {
		i = BnCmp(r, m, digs)
		if i == -1 {
			break
		}

		if i == 0 {
			*r = Bn0
			break
		} else {
			i = BnGetBits(r, digs) - n
			tmp = *m
			if i > 1 {
				BnLshBits(&tmp, m, i-1, digs)
			}
			BnSubBasic(r, r, &tmp, digs)
		}
	}
}

func BnModAdd(r *BN, x *BN, y *BN, m *BN, digs int) {
	var tmp BN
	var carry DigT

	BnMod(&tmp, x, m, digs)
	BnMod(r, y, m, digs)

	carry = BnAddBasic(r, &tmp, r, digs)
	if carry > 0 || BnCmp(r, m, digs) != -1 {
		BnSubBasic(r, r, m, digs)
	}
}

func BnModSub(r *BN, x *BN, y *BN, m *BN, digs int) {
	var tmp BN

	BnMod(&tmp, x, m, digs)
	BnMod(r, y, m, digs)

	if BnCmp(&tmp, r, digs) == 1 {
		BnSubBasic(r, &tmp, r, digs)
	} else {
		BnAddBasic(&tmp, &tmp, m, digs)
		BnSubBasic(r, &tmp, r, digs)
	}
}

// BnMontInit Computes Montgomery Const (the reciprocal of the modulus) to be used
// in the Montgomery reduction algorithm, which needs the modulus is odd.
func BnMontInit(mc *DigT, m *BN) int {
	var c DigT

	if m[0]&1 == 0 {
		// ERR_NO_VALID
		return -1
	}

	c = 1
	for i := 1; i < 32; i++ {
		c = c * c * m[0]
	}

	*mc = 0xffffffff - c + 1
	return 0
}

func BnInitMontRRm(rrm *BN, m *BN, digs int) {
	var bits = BnGetBits(m, digs)
	if bits%32 > 0 {
		bits = bits + 32 - (bits % 32)
	}
	BnSetDig(rrm, 1, digs)
	BnLshBits(rrm, rrm, bits-1, digs)
	BnModAdd(rrm, rrm, rrm, m, digs)

	for ; bits > 0; bits-- {
		BnModAdd(rrm, rrm, rrm, m, digs)
	}
}

func BnMontMul(r *BN, x *BN, y *BN, m *BN, mc DigT, digs int) {
	var q DigT
	var carry DigT
	var carryH DigT
	var carryT DigT
	var d BN

	for digs > 0 && m[digs-1] == 0 {
		digs--
	}

	carryH = 0
	for i := 0; i < digs; i++ {
		carry = carryH
		q = (x[0]*y[i] + d[0]) * mc

		carryT = bnMulDigAddBn(&d, x, &d, y[i], digs)
		carryH, carry = DigAddDig(carry, carryT)

		carryT = bnMulDigAddBn(&d, m, &d, q, digs)
		q, carry = DigAddDig(carry, carryT)
		carryH += q

		bnRsh32bit(&d, digs)
		d[digs-1] = carry
	}

	if carryH == 1 {
		BnSubBasic(r, &Bn0, m, digs)
		BnAddBasic(r, r, &d, digs)
	} else if BnCmp(&d, m, digs) != -1 {
		BnSubBasic(r, &d, m, digs)
	} else {
		*r = d
	}
}

// BnMontRdc computes r = BnMontMul(x, 1, m)
func BnMontRdc(r *BN, x *BN, m *BN, mc DigT, digs int) {
	BnMontMul(r, x, &Bn1, m, mc, digs)
}

// BnMontExp computes r = pow(x, e, m)
// where VLNW is used
func BnMontExp(r *BN, x *BN, e *BN, m *BN, mc DigT, digs int) {
	var bits, i, j int
	var bit uint8
	var LF, LW, buf uint8
	var nwOrZw int

	/* precompute */
	var xExp1 BN
	var xExp3 BN
	var xExp5 BN
	var xExp7 BN
	var xExp9 BN
	var xExp11 BN
	var xExp13 BN
	var xExp15 BN
	var xExp17 BN
	var xExp19 BN
	var xExp21 BN
	var xExp23 BN
	var xExp25 BN
	var xExp27 BN
	var xExp29 BN
	var xExp31 BN

	var tmp BN

	var window [Sm2CurveSize * 8][2]uint8

	xExp1 = *x

	/* pow(x, 2, m) */
	BnMontMul(&tmp, x, x, m, mc, digs)

	/* pow(x, 3, m) */
	BnMontMul(&xExp3, &xExp1, &tmp, m, mc, digs)
	/* pow(x, 5, m) */
	BnMontMul(&xExp5, &xExp3, &tmp, m, mc, digs)
	/* pow(x, 7, m) */
	BnMontMul(&xExp7, &xExp5, &tmp, m, mc, digs)
	/* pow(x, 9, m) */
	BnMontMul(&xExp9, &xExp7, &tmp, m, mc, digs)
	/* pow(x, 11, m) */
	BnMontMul(&xExp11, &xExp9, &tmp, m, mc, digs)
	/* pow(x, 13, m) */
	BnMontMul(&xExp13, &xExp11, &tmp, m, mc, digs)
	/* pow(x, 15, m) */
	BnMontMul(&xExp15, &xExp13, &tmp, m, mc, digs)
	/* pow(x, 17, m) */
	BnMontMul(&xExp17, &xExp15, &tmp, m, mc, digs)
	/* pow(x, 19, m) */
	BnMontMul(&xExp19, &xExp17, &tmp, m, mc, digs)
	/* pow(x, 21, m) */
	BnMontMul(&xExp21, &xExp19, &tmp, m, mc, digs)
	/* pow(x, 23, m) */
	BnMontMul(&xExp23, &xExp21, &tmp, m, mc, digs)
	/* pow(x, 25, m) */
	BnMontMul(&xExp25, &xExp23, &tmp, m, mc, digs)
	/* pow(x, 27, m) */
	BnMontMul(&xExp27, &xExp25, &tmp, m, mc, digs)
	/* pow(x, 29, m) */
	BnMontMul(&xExp29, &xExp27, &tmp, m, mc, digs)
	/* pow(x, 31, m) */
	BnMontMul(&xExp31, &xExp29, &tmp, m, mc, digs)

	bits = BnGetBits(e, digs)
	nwOrZw = 0 // 此次分类进入nw还是zw
	buf = 0
	LF = 0
	LW = 0

	for i = 0; i < bits; i++ {
		bit = (uint8)(e[i>>5]>>(i&0b11111)) & 0x1

		if nwOrZw == 0 {
			if bit == 0 {
				LF++
			} else {
				if LF > 0 {
					window[LW][0] = LF
					window[LW][1] = buf
					LW++
				}

				buf = 0
				LF = 0
				nwOrZw = 1
			}
		}

		if nwOrZw == 1 {
			buf = (bit << LF) | buf
			LF++

			if LF == WindowD {
				j = WindowD - 1
				for j > 0 {
					if ((buf >> j) & 1) == 0 {
						i--
						j--
						LF--
						continue
					}
					break
				}

				window[LW][0] = LF
				window[LW][1] = buf
				LW++

				buf = 0
				LF = 0
				nwOrZw = 0
			}
		}
	}

	if LF != 0 {
		window[LW][0] = LF
		window[LW][1] = buf
		LW++
	}

	switch {
	case window[LW-1][1] == 1:
		tmp = xExp1
	case window[LW-1][1] == 3:
		tmp = xExp3
	case window[LW-1][1] == 5:
		tmp = xExp5
	case window[LW-1][1] == 7:
		tmp = xExp7
	case window[LW-1][1] == 9:
		tmp = xExp9
	case window[LW-1][1] == 11:
		tmp = xExp11
	case window[LW-1][1] == 13:
		tmp = xExp13
	case window[LW-1][1] == 15:
		tmp = xExp15
	case window[LW-1][1] == 17:
		tmp = xExp17
	case window[LW-1][1] == 19:
		tmp = xExp19
	case window[LW-1][1] == 21:
		tmp = xExp21
	case window[LW-1][1] == 23:
		tmp = xExp23
	case window[LW-1][1] == 25:
		tmp = xExp25
	case window[LW-1][1] == 27:
		tmp = xExp27
	case window[LW-1][1] == 29:
		tmp = xExp29
	case window[LW-1][1] == 31:
		tmp = xExp31

	default:
		tmp = Bn0
	}

	for i = int(LW) - 2; i >= 0; i-- {
		for j = 0; j < int(window[i][0]); j++ {
			BnMontMul(&tmp, &tmp, &tmp, m, mc, digs)
		}

		switch {
		case window[i][1] == 1:
			BnMontMul(&tmp, &tmp, &xExp1, m, mc, digs)
		case window[i][1] == 3:
			BnMontMul(&tmp, &tmp, &xExp3, m, mc, digs)
		case window[i][1] == 5:
			BnMontMul(&tmp, &tmp, &xExp5, m, mc, digs)
		case window[i][1] == 7:
			BnMontMul(&tmp, &tmp, &xExp7, m, mc, digs)
		case window[i][1] == 9:
			BnMontMul(&tmp, &tmp, &xExp9, m, mc, digs)
		case window[i][1] == 11:
			BnMontMul(&tmp, &tmp, &xExp11, m, mc, digs)
		case window[i][1] == 13:
			BnMontMul(&tmp, &tmp, &xExp13, m, mc, digs)
		case window[i][1] == 15:
			BnMontMul(&tmp, &tmp, &xExp15, m, mc, digs)
		case window[i][1] == 17:
			BnMontMul(&tmp, &tmp, &xExp17, m, mc, digs)
		case window[i][1] == 19:
			BnMontMul(&tmp, &tmp, &xExp19, m, mc, digs)
		case window[i][1] == 21:
			BnMontMul(&tmp, &tmp, &xExp21, m, mc, digs)
		case window[i][1] == 23:
			BnMontMul(&tmp, &tmp, &xExp23, m, mc, digs)
		case window[i][1] == 25:
			BnMontMul(&tmp, &tmp, &xExp25, m, mc, digs)
		case window[i][1] == 27:
			BnMontMul(&tmp, &tmp, &xExp27, m, mc, digs)
		case window[i][1] == 29:
			BnMontMul(&tmp, &tmp, &xExp29, m, mc, digs)
		case window[i][1] == 31:
			BnMontMul(&tmp, &tmp, &xExp31, m, mc, digs)
		}
	}

	*r = tmp
}
